Gottesman–Knill theorem

In quantum computing, the Gottesman–Knill theorem is a theoretical result that states that an important subclass of quantum circuits, called stabilizer circuits, can be simulated efficiently. That is simulation of QC algorithms that use only these circuits can be run in polynomial time on a classical computer. Stabilizer circuits are circuits that use only gates from the Clifford group subset of quantum gates.

Formal statement

Theorem: A quantum circuit using only the following elements can be simulated efficiently on a classical computer:

1. Preparation of qubits in computational basis states,
2. Quantum gates from the Clifford group (Hadamard gates, controlled NOT gates, Pauli gates), and
3. Measurements in the computational basis.

The Gottesman–Knill theorem shows that even some highly entangled states can be simulated efficiently. Several important types of QC algorithms use only Clifford gates, most importantly the standard algorithms for entanglement purification and for quantum error correction. From a practical point of view, stabilizer circuits have been simulated in O(n log n) time using the graph state formalism.

References

• S. Anders and H. J. Briegel (2006). "Fast simulation of stabilizer circuits using a graph-state representation". Phys. Rev. A 73: 022334. arXiv:quant-ph/0504117v2. doi:10.1103/PhysRevA.73.022334. 

• Quantum Computation and Quantum Information, Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000